package com.demo.java.OD451_500.OD471;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【二叉树计算(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146353831
 */
public class OdMain {
    // 构建二叉树的方法
    public static Map<String, Object> buildTree(List<Integer> inorder,
                                                List<Integer> preorder) {
        if (inorder.isEmpty() || preorder.isEmpty())
            return null;

        int rootVal = preorder.remove(0); // 获取前序遍历的根节点
        int rootIndex = inorder.indexOf(rootVal); // 在中序遍历中找到根节点的位置
        Map<String, Object> root = new HashMap<>();
        root.put("val", rootVal); // 将根节点的值存入
        root.put("left", buildTree(inorder.subList(0, rootIndex), preorder)); // 构建左子树
        root.put("right", buildTree(inorder.subList(rootIndex + 1, inorder.size()), preorder)); // 构建右子树
        return root;
    }

    // 计算每个节点的值，节点值为左右子树的节点值之和
    public static void calculateNodeValues(Map<String, Object> root) {
        if (root == null)
            return;

        // 计算当前节点的值
        root.put("val", calculateSum((Map<String, Object>) root.get("left")) +
                calculateSum((Map<String, Object>) root.get("right")));
        calculateNodeValues((Map<String, Object>) root.get("left")); // 递归计算左子树
        calculateNodeValues((Map<String, Object>) root.get("right")); // 递归计算右子树
    }

    // 计算树的总和
    public static int calculateSum(Map<String, Object> root) {
        if (root == null)
            return 0;

        return (int) root.get("val") + calculateSum((Map<String, Object>) root.get("left")) + calculateSum((Map<String, Object>) root.get("right"));
    }

    // 中序遍历树，输出节点值
    public static void inorderTraversal(Map<String, Object> root) {
        if (root == null)
            return;

        inorderTraversal((Map<String, Object>) root.get("left")); // 递归遍历左子树
        System.out.print(root.get("val") + " "); // 打印当前节点的值
        inorderTraversal((Map<String, Object>) root.get("right")); // 递归遍历右子树
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] inorderStr = scanner.nextLine().split(" "); // 读取中序遍历
        String[] preorderStr = scanner.nextLine().split(" "); // 读取前序遍历

        // 将中序遍历和前序遍历转换为整数列表
        List<Integer> inorder = new ArrayList<>();
        List<Integer> preorder = new ArrayList<>();

        for (String str : inorderStr)
            inorder.add(Integer.parseInt(str));

        for (String str : preorderStr)
            preorder.add(Integer.parseInt(str));

        // 构建二叉树
        Map<String, Object> root = buildTree(inorder, preorder);
        calculateNodeValues(root); // 计算节点值
        inorderTraversal(root); // 中序遍历输出节点值
    }
}